二叉搜索树与双向链表

二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

• 转换结点，并将pLast指针朝中序遍历（即排序方向）移动。

  function Convert(pRootOfTree)
  {
      // write code here
      if(pRootOfTree===null)return null;
      let pLast=null;
      pLast=ConvertNode(pRootOfTree,pLast);
      let pHead=pLast;
      while(pHead&&pHead.left){
          pHead=pHead.left;
      }
      return pHead;
  }
  function ConvertNode(pNode,pLast){
      if(pNode===null)return ;
      if(pNode.left){
          pLast=ConvertNode(pNode.left,pLast);
      }
      pNode.left=pLast;
      if(pLast){
          pLast.right=pNode;
      }
      pLast=pNode;
      if(pNode.right){
          pLast=ConvertNode(pNode.right,pLast);
      }
      return pLast;
  }